package com.fps.webshop.question.question0001_0099;

/**
 * 9. 回文数
 * 
 * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
 * 
 * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
 * 
 * 示例 1：
 * 输入：x = 121
 * 输出：true
 * 
 * 示例 2：
 * 输入：x = -121
 * 输出：false
 * 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
 * 
 * 示例 3：
 * 输入：x = 10
 * 输出：false
 * 解释：从右向左读, 为 01 。因此它不是一个回文数。
 * 
 * 示例 4：
 * 输入：x = -101
 * 输出：false
 * 
 * 提示：
 * -2^31 <= x <= 2^31 - 1
 * 
 * 进阶：你能不将整数转为字符串来解决这个问题吗？
 */
public class Question009 {

	/**
	 * 第一次提交，依旧使用转换成字符串进行尝试，通过了，但相对来说太耗时了
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		15 ms	38.1 MB	Java	2021/08/06 13:30
	 */
	public static boolean isPalindrome1(int x) {
		Boolean isF = true;
		if(x<0) {
			return false;
		}else if(x==0) {
			return true;
		}else {
			String xs = x+"";
			int length = xs.length()%2;
			if(length==0) {
				//双数
				int start = xs.length()/2-1;
				int end = xs.length()/2;
				for(;start>=0;start--,end++) {
					if(xs.charAt(start)!=xs.charAt(end)) {
						isF = false;
						break;
					}
				}
			}else {
				//单数
				int start = xs.length()/2-1;
				int end = xs.length()/2+1;
				if(start<0||end>xs.length()) {
					return true;
				}else {
					for(;start>=0;start--,end++) {
						if(xs.charAt(start)!=xs.charAt(end)) {
							isF = false;
							break;
						}
					}
				}
			}
			return isF;
		}
    }
	
	/**
	 * 第二次提交，将使用String.charAt查询修改为先将String转化成char[]，再通过数组查找，但时间消耗没有减少
	 * 反而增加了内存消耗，不可取
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		15 ms	38.5 MB	Java	2021/08/06 13:34
	 */
	public static boolean isPalindrome2(int x) {
		Boolean isF = true;
		if(x<0) {
			return false;
		}else if(x==0) {
			return true;
		}else {
			String xs = x+"";
			char[] sss = xs.toCharArray();
			int length = xs.length()%2;
			if(length==0) {
				//双数
				int start = xs.length()/2-1;
				int end = xs.length()/2;
				for(;start>=0;start--,end++) {
					if(sss[start]!=sss[end]) {
						isF = false;
						break;
					}
				}
			}else {
				//单数
				int start = xs.length()/2-1;
				int end = xs.length()/2+1;
				if(start<0||end>xs.length()) {
					return true;
				}else {
					for(;start>=0;start--,end++) {
						if(sss[start]!=sss[end]) {
							isF = false;
							break;
						}
					}
				}
			}
			return isF;
		}
    }
	
	/**
	 * 第三次提交，利用之前整数反转的思想
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		9 ms	37.7 MB	Java	2021/08/06 13:44
	 */
	public static boolean isPalindrome3(int x) {
		if(x<0) {
			return false;
		}else if(x==0) {
			return true;
		}else {
			long sum = 0;
			int begin = x;
	        while(x != 0) {
	        	sum = sum*10 + x%10;
	            x = x/10;
	        }
			if(sum > Integer.MAX_VALUE || sum < Integer.MIN_VALUE) {
				return false;
			}
			return (int)sum==begin;
		}
    }
	
	/**
	 * 第四次提交，利用之前整数反转的思想，再稍微去掉多余代码
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		8 ms	38 MB	Java	2021/08/06 13:45
	 */
	public boolean isPalindrome(int x) {
        if(x<0) {
			return false;
		}else if(x==0) {
			return true;
		}else {
			int sum = 0;
			int begin = x;
	        while(x != 0) {
	        	sum = sum*10 + x%10;
	            x = x/10;
	        }
			return sum==begin;
		}
    }
	
	public static void main(String[] args) {
		System.out.print(isPalindrome3(121));
	}
}
